//给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "abcabcbb"
//输出: 3 
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
// 
//
// 示例 2: 
//
// 
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
// 
//
// 示例 3: 
//
// 
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 5 * 10⁴ 
// s 由英文字母、数字、符号和空格组成 
// 
//
// Related Topics 哈希表 字符串 滑动窗口 👍 7965 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution3 {

    /**
     * 滑动窗口标准写法：
     * //外层循环扩展右边界，内层循环扩展左边界
     * for (int l = 0, r = 0 ; r < n ; r++) {
     * 	//当前考虑的元素
     * 	while (l <= r && check()) {//区间[left,right]不符合题意
     *         //扩展左边界
     *     }
     *     //区间[left,right]符合题意，统计相关信息
     * }
     * @param s
     * @return
     */
//    public int lengthOfLongestSubstring(String s) {
//        char[] chars = s.toCharArray();
//        Set<Character> set = new HashSet<>();
//        int result = 0;
//        for(int left = 0, right = 0; right < chars.length; right++) {
//            char c = chars[right];
//            while(set.contains(c)){
//                set.remove(chars[left]);
//                left++;
//            }
//            set.add(c);
//            result = Math.max(result, right - left + 1);
//        }
//        return result;
//    }

    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        if (chars.length <= 1) return chars.length;
        Map<Character, Integer> map = new HashMap<>();
        int result = 0;
        int[] dp = new int[chars.length];
        dp[0] = 1;
        map.put(chars[0], 0);
        int leftIndex = 0;

        for(int i = 1; i < chars.length; i++) {
            if (map.containsKey(chars[i])) {
                leftIndex = Math.max(leftIndex, map.get(chars[i]));
                dp[i] = i - leftIndex;
            } else {
                dp[i] = dp[i-1] + 1;
            }
            map.put(chars[i], i);
            result = Math.max(result, dp[i]);
        }
        return result;
    }


//    public int lengthOfLongestSubstring(String s) {
//        Map<Character, Integer> map = new HashMap<>();
//        int left = 0, right = 0;
//        int ans = 0;
//        while(right < s.length()){
//            char c = s.charAt(right);
//            if(map.containsKey(c) && map.get(c) > 0){
////                ans = Math.max(ans, right - left);
//                char c1 = s.charAt(left);
//                map.put(c1, map.get(c1) - 1);
//                left++;
//            } else {
//                map.put(c, map.getOrDefault(c, 0)+1);
//                right++;
//            }
//            ans = Math.max(ans, right - left);
//        }
//        return ans;
//    }

    public static void main(String[] args) {
        int i = new Solution3().lengthOfLongestSubstring("abcba");
        System.out.println(i);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
